//
//  SearchSolution.hpp
//  leetcode
//
//  Created by Ellie on 2021/2/7.
//  Copyright © 2021 Ellie. All rights reserved.
//

#ifndef SearchSolution_hpp
#define SearchSolution_hpp

#include "DataDefine.h"
#include <queue>
#include <unordered_map>
#include <string>
#include <stack>
#include <vector>
#include <deque>
#include <iostream>
#include <sstream>

using namespace std;

class SearchSolution
{
public:
    // 二分查找算法
    // binary search
    // 二分查找，在顺序数组中查找对应的值
    // 逐步将结果收敛到一侧，不断的逼近结果
    int binarySearch(vector<int>& input, int value);
    int binarySearchRecursion(vector<int>& input, int value, int low, int high);
    // 查找第一个=value的元素34. 在排序数组中查找元素的第一个和最后一个位置
    int binarySearchFirstOfIndex(vector<int>& input, int target);
    // 查找最后一个=value的元素34. 在排序数组中查找元素的第一个和最后一个位置
    int binarySearchLastOfIndex(vector<int>& input, int target);
    // 查找大于等于value的第一个元素
    int binarySerachFirstGreaterOrEqualIndex(vector<int>& nums, int target);
    // 查找最后一个小于等于value的元素
    int binarySerachLastLessOrEqualIndex(vector<int>& nums, int target);
    
    /*
    1. 704. 二分查找 递归和迭代，基础二分算法
    2. 35. 搜索插入位置
    3. 153. 寻找旋转排序数组中的最小值
    4. 81. 搜索旋转排序数组 II
    5. 33. 搜索旋转排序数组
    6. 34. 在排序数组中查找元素的第一个和最后一个位置
     */
    int leetcode35searchInsert(vector<int>& input, int target);
    
    // 旋转数组最小值问题，最小值=旋转点
    // 153. 寻找旋转排序数组中的最小值 并不是查找元素
    int findMin(vector<int>& nums);
    // 154. 寻找旋转排序数组中的最小值 II 并不是查找元素，元素不唯一，如果相同high--，去掉一个干扰的元素
    int findMin154(vector<int>& nums);
    
    // 33. 搜索旋转排序数组 查找元素，元素唯一
    int search33(vector<int>& nums, int target);
    // 81. 搜索旋转排序数组 II，查找元素，元素不唯一，是否包含target元素
    bool search81(vector<int>& nums, int target);
    // 34. 在排序数组中查找元素的第一个和最后一个位置
    vector<int> searchRange(vector<int>& nums, int target);
    
};

#endif /* SearchSolution_hpp */
